[Kryptografia] Affine transformation

Zapraszam, zapraszam ... kolejny niezrównoważony pseudomatematyczny bełkot. Co chwilę wpadam w dygresję i przekraczam wszelkie rozsądne rozmiary postu.

W gruncie rzeczy sądzę, że teoria liczb jest świetnym kandydatem na najtrudniejszą gałąź matematyki. Zdecydowanie jesteśmy bardziej bezbronni wobec krwiożerczej i przerażającej sumy uogólnionej niż ledwo niegrzecznej całki.

Zapraszam do lektury !

"mod" może mieć dwa znaczenia:

reszta w dzieleniu całkowitoliczbowym (np. Delphi).
x = 12 mod 10
tutaj x jest jedną liczbą = 2

przystawanie dwóch liczb (kongruencja)
x = 12 (mod 10)
tutaj x może przyjąć jedną z nieskończenie wielu wartości = {2, 12, 22, 32, ...}.
Reguła jest następująca:
reszta z dzielenia x przez 10 jest taka sama jak reszta z dzielenia 12 przez 10 (czyli 2).

Jeszcze jeden przykład:
5 mod 4 = 1
5 (mod 4) = 1 lub 5 lub 9 ...

Jest więc pewna subtelna różnica w zapisie i będę ją uwzględniał w dalszej części tekstu.

Pierwszy pomysł
Dryo, prawdopodobnie miałeś na myśli równanie:
c = a*k (mod n)

Chcemy wyznaczyć wartość a. Pierwszy pomysł polega na wykorzystaniu dwóch praw:

jeśli a = b (mod n) to

1. b = a (mod n)
2. a:d = b:d (mod n:d) przy czym a, b i n są podzielne przez liczbę naturalną d

Możemy więc zapisać
a*k = c (mod n)
a = c:k (mod n:k)

Niestety, wbrew pozorom nie przybliżyliśmy się do rozwiązania ani trochę. Wynika to z dwóch faktów:

1. c oraz n muszą być podzielne przez k
2. z treści zadania wiemy że n i k są wzglęnie pierwsze

Liczby względnie pierwsze to takie, których największy wspólny dzielnik wynosi 1.

Inaczej nwd(n,k)=1
W związku z tym k nie jest podzielnikiem n, gdyż wtedy nwd(n,k)=k
Inaczej mówiąc n nie jest podzielny przez k - nie możemy więc zastosować drugiego z przytoczonych praw kongruencji.

Szukamy brutalną siłą
Rozwiązanie problemu istnieje i uprzedzając powiem że prowadzi przez tzw. odwrotny algorytm Euklidesa. Wpierw jednak rozpracujmy przykład:

c = ak (mod n)
7 = a3 (mod 8)

Wartości c, a i n są ograniczone na dwa sposoby:

1. nwd(n,k) = 1
2. c < n

Drugie wynika z tego, że reszta z dzielenia przez np. 8 może w największym przypadku wynosić 7.

Wracamy do przykładu, mamy
7 = a*3 (mod 8)

Pytamy więc: Dla jakiej wartości a reszta z dzielenia 3*a przez 8 wynosi 7. Sprawdźmy dla kilku wartości:

a 3*a mod 8

1 3
2 6
3 1
4 4
5 7
6 2
7 5
8 0
9 3
10 6

Jedną z możliwych odpowiedzi jest więc a=7

A ile wynosi 3*11 mod 8 ?
bez liczenia możemy powiedzieć: 1

ciąg 3, 6, 1, 4, 7, 2, 5, 0 powtarza się cyklicznie a każda wartość z zakresu [0, 7] występuje w nim dokładnie jeden raz (analogię tego zjawiska znajdziemy w tablicach haszujących - a dokładniej w jednej z popularnych strategi obsługi kolizji)

Spróbujmy teraz zobaczyć co się stanie gdy odrzucimy warunek nwd(n,k)=1, np.
7=a*4 (mod 8)

a 4*a mod 8

1 4
2 0
3 4

Zauważmy że nie istnieje rozwiązanie równania 7=4*a (mod 8)

Można to skojarzyć z długością cyklu, która w ogólnym przypadku wynosi:
n / nwd(k,n)

... faktycznie
n / nwd(k,n) = 8 / nwd(4,8) = 8/4 = 2

W związku z tym możemy wywnioskować, że:
Warunek nwd(n,k)=1 jest warunkiem wystarczającym rozwiązywalności równania (ale nie koniecznym, gdyż np. równianie 4=4a (mod 8) rozwiązanie posiada).

Rozwiązanie
(Prawdopodobnie bardziej niecierpliwi już dawno zarzucili czytanie.)

Wychodzimy od problemu:
c = k*a (mod n)
a = ?

Gdybyśmy potrafili wyrazić c za pomocą wyrażenia:
c = kx - ny

To okaże się, że wartość x jest jednym z możliwych rozwiązań !

Oto dowód:
Podstawiamy do wzoru c = ka (mod n)
kx - ny = ka (mod n)

korzystamy z pierwszej własności kongruencji:
ka = kx - n*y (mod n)

Na chwilę się zatrzymajmy
Czy jest jakaś różnica pomiędzy:
24 (mod 10)
14 (mod 10)
4 (mod 10) ?

Nie ! Każde z nich definiuje ten sam zbiór rozwiązań = {4, 14, 24, 34 ...}
W związku z tym możemy napisać że
241 - 100 (mod 10) =
241 - 101 (mod 10) =
241 - 102 (mod 10)

a bardziej ogólnie:
kx - ny (mod n) =
kx - n0 (mod n) =
k*x (mod n)

teraz podstawiając otrzymujemy:
ka = kx (mod n)

a to oznacza że:
a=x

Podsumowując, jeśli wyrazimy c za pomocą wyrażenia:
c = kx - ny

to x jest jednym z rozwiązań.

Sposób
Wspominałem o odwrotnym algorytmie Euklidesa - ta potoczna nazwa jest odrobinę myląca. W istocie jego działanie rozpoczyna się w miejscu, w którym klasyczny algorytm Euklidesa się kończy.

posłużę się przykładem (tym samym co pierwsza tabelka):

7 = 3a (mod 8)
a = ?

Będziemy chcieli więc przedstawić c=7 jako
c = kx - ny
7 = 3x - 8y

Zaczynamy od zastosowania algorytmu Euklidesa dla wartości n i k. Może wydawać się to głupie, gdyż wynik tego działania jest z góry znany - nwd(n,k)=1 z treści zadania.

Jednak tak naprawdę nie interesuje nas wynik, tylko droga którą do niego dochodzimy:

8 = 23 + [color=red]2[/color]
3 = 12 + [color=red]1[/color]
2 = 2*1 + 0

Zanim wyrazimy 7 jako
7 = 3x - 8y

wpierw rozpiszemy
1 = 3x' - 8y'

robimy to w oparciu o przedostatni wiersz algorytmu Euklidesa:
[color=red]1[/color] = 3 - 1*[color=red]2[/color]
1 = 3 - 1*(8 - 23)
1 = 33 - 8*1

wystarczy teraz przemnożyć stronami
7 = 321 - 87

odpowiedź: rozwiązaniem 7 = 3*a (mod 8) jest między innymi liczba 21
sprawdzenie: w istocie 7 = 63 (mod 8) [czytaj "7 przystaje do 63 modulo 8"]

Uogólnienie
A jeśli szukamy najmniejszego możliwego a ?

• inaczej mówiąc jeśli szukamy rozwiązania 7 = 3*a mod 8
  Jest nim x mod n
  czyli 21 mod 8 = 5

W ogólności a = { a1, a1 + n, a1 + 2n, ... a1 + kn }
gdzie a1=x mod n
(x jest wynikiem naszego algorytmu)

Pozdrawiam bardzo gorąco
kapustka